package Arithmetic;

import java.util.Arrays;
import java.util.HashMap;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 34255
 * Date: 2024-11-10
 * Time: 10:18
 */
//动态规划
public class DynamicPlanning {
    //1137.第N个泰波那契数列
    public static int tribonacci(int n) {

        //保证数组的后面的使用不会越界
        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;

        //创建dp表
        int[] dp = new int[n + 1];//n + 1才能表示第n个数

        //保证填表的时候不越界
        dp[0] = 0;dp[1] = 1;dp[2] = 1;

        //初始化dp表(填表)
        for(int i = 3;i <= n;i++){
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

        //返回返回值
        return dp[n];
    }

    //面试题 08.01. 三步问题
    public static int waysToStep(int n) {
        //创建dp数组
        int[] dp = new int[n + 1];

        //避免dp数组的使用时数组越界
        if(n == 1 || n == 2) return n;
        if(n == 3) return 4;

        //防止数组越界
        dp[1] = 1;dp[2] = 2;dp[3] = 4;

        int MOD = (int)1e9 + 7;

//初始化dp数组
        for(int i = 4;i <= n;i++)
            //避免结果过大，每次计算出和就模上MOD
            dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;

        //返回返回值
        return dp[n];
    }

    //746. 使用最小花费爬楼梯  解法一
    public static int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        //创建dp[]数组
        int[] dp = new int[n];

        //初始化，防止数组越界
        dp[n - 1] = cost[n - 1];dp[n - 2] = cost[n - 2];

        //填表
        for(int i = n - 3;i >= 0;i--)
            dp[i] = Math.min(dp[i + 1] + cost[i],dp[i + 2] + cost[i]);

        return Math.min(dp[0],dp[1]);
    }

    //746. 使用最小花费爬楼梯  解法二
    public static int minCostClimbingStairs1(int[] cost) {
        //创建dp[]数组
        int[] dp = new int[cost.length + 1];

        //初始化，防止数组越界
        dp[0] = dp[1] = 0;

        //填表
        for(int i = 2;i < dp.length;i++)
            dp[i] = Math.min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);

        return dp[dp.length - 1];
    }

    //91.解码方式
    public static int numDecodings(String s) {
        int n = s.length();
        //创建dp[]数组
        int[] dp = new int[n];

        //防止数组越界
        if(s.charAt(0) != '0'){
            dp[0] = 1;
            if(n == 1)
                return dp[0];
        }else{
            return 0;
        }

        if(dp[0] == '0') dp[1] = 0;
        else if(Integer.valueOf(s.substring(0,2)) > 26) dp[1] = 1;
        else dp[1] = 2;

        //填表
        for(int i = 2;i < n;i++){
            //单独解码
            if(s.charAt(i) == '0') dp[i] = 0;
            else dp[i] += dp[i - 1];

            //组合解码
            if(s.charAt(i - 1) == '0' || Integer.valueOf(s.substring(i-1,i+1)) > 26) dp[i] = 0;
            else dp[i] += dp[i - 2];
        }

        return dp[n - 1];
    }

    //1576.替换所有的问号
    public static String modifyString(String ss) {
        char[] s = ss.toCharArray();
        for(int i = 0;i < s.length;i++){
            if(s[i] == '?'){
                for(char j = 'a';j <= 'z';j++){
                    if((i == 0 || j != s[i - 1]) && (i == s.length - 1 || j != s[i + 1])){
                        s[i] = j;
                        break;
                    }
                }
            }
        }
        return new String(s);
    }

    //62.不同路径
    public static int uniquePaths(int mm, int nn) {
        //添加虚拟节点，并初始化，处理边界问题
        int m = mm + 1;
        int n = nn + 1;

        int[][] dp = new int[m + 1][n + 1];
        dp[0][1] = 1;

        //填表
        for(int i = 1;i < m;i++){
            for(int j = 1;j < n;j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[mm][nn];
    }

    //63.不同路径II
    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        //创建dp[][]数组,并增加虚拟节点，处理边界情况
        int[][] dp = new int[m + 1][n + 1];
        //初始化
        dp[0][1] = 1;

        //填表
        for(int i = 1;i <= m;i++){
            for(int j = 1;j <= n;j++){
                //判断是否为障碍点
                if(obstacleGrid[i - 1][j - 1] == 1)
                    dp[i][j] = 0;
                else
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }

    //LCR 166.珠宝的最高价值
    public static int jewelleryValue(int[][] frame) {
        int m = frame.length;
        int n = frame[0].length;

        //创建dp数组
        int[][] dp = new int[m + 1][n + 1];

        //填表
        for(int i = 1;i <= m;i++){
            for(int j = 1;j <= n;j++)
                dp[i][j] = Math.max(dp[i - 1][j] + frame[i - 1][j - 1],dp[i][j - 1] + frame[i - 1][j - 1]);
        }

        return dp[m][n];
    }

    //931.下降路径最小和
    public static int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        //创建dp数组
        int[][] dp = new int[m + 1][n + 2];

        //初始化，处理边界问题
        for(int i = 1;i < m;i++){
            dp[i][0] = dp[i][n + 1] = Integer.MAX_VALUE;
        }

        //填表
        for(int i = 1;i <= m;i++){
            for(int j = 0;j <= n;j++){
                dp[i][j] = Arrays.stream(new int[]{dp[i - 1][j - 1],dp[i - 1][j],dp[i - 1][j + 1]}).min().getAsInt() + matrix[i][j];
            }
        }

        return Arrays.stream(Arrays.copyOfRange(dp[m], 1, n + 1)).min().getAsInt();
    }

    //174.地下城游戏
    public static int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;

        //创建dp表,处理边界问题
        int[][] dp = new int[m + 1][n + 1];

        dp[m][n - 1] = dp[m - 1][n] = 1;
        for(int i = 0;i < m - 1;i++)
            dp[i][n] = Integer.MAX_VALUE;
        for(int i = 0;i < n - 1;i++)
            dp[m][i] = Integer.MAX_VALUE;

        //填表
        for(int i = m - 1;i >= 0;i--){
            for(int j = n - 1;j >= 0;j--){
                dp[i][j] = Math.min(dp[i][j + 1],dp[i + 1][j]) - dungeon[i][j];
                //防止出现血包太大，出现负数的情况
                dp[i][j] = Math.max(1,dp[i][j]);
            }
        }
        return dp[0][0];
    }

    //面试题 17.16.按摩师按摩师
    public static int massage(int[] nums) {
        if(nums.length == 0) return 0;
        int n = nums.length;
        //创建多dp表,处理边界问题
        int[] f = new int[n];
        int[] g = new int[n];

        f[0] = nums[0];
        g[0] = 0;

        //填表
        for(int i = 1;i < n;i++){
            f[i] = nums[i] + g[i - 1];
            g[i] = Math.max(f[i - 1],g[i - 1]);
        }

        return Math.max(f[n - 1],g[n - 1]);
    }

    //打家劫舍II
    public static int rob(int[] nums) {
        int n = nums.length;
        if(n == 1) return nums[0];

        //创建f,g数组
        int[] f = new int[n];
        int[] g = new int[n];

        //1.偷0的情况
        //初始化
        f[0] = g[1] = nums[0];
        f[1] = 0;

        //填表
        for(int i = 2;i < n - 1;i++){
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(g[i - 1],f[i - 1]);
        }

        int tempMax = Math.max(g[n - 2],f[n - 2]);

        //不偷0情况
        //初始化
        f[0] = g[0] = 0;
        //填表
        for(int i = 1;i < n;i++){
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(g[i - 1],f[i - 1]);
        }

        return Math.max(tempMax,Math.max(g[n - 1],f[n - 1]));
    }

    //LCR 091.粉刷房子
    public static int minCost(int[][] costs) {
        int n = costs.length;

        //创建dp数组
        int[][] dp = new int[n + 1][3];

        //填表
        for(int i = 1;i <= n;i++){
            dp[i][0] = costs[i - 1][0] + Math.min(dp[i - 1][1],dp[i - 1][2]);
            dp[i][1] = costs[i - 1][1] + Math.min(dp[i - 1][0],dp[i - 1][2]);
            dp[i][2] = costs[i - 1][2] + Math.min(dp[i - 1][1],dp[i - 1][0]);
        }

        return Arrays.stream(dp[n]).min().getAsInt();
    }

    //121.买卖股票的最佳时机
    public static int maxProfit(int[] prices) {
        int n = prices.length;

        //创建dp数组
        int[][] dp = new int[n][2];

        //初始化
        dp[0][0] = -prices[0];

        for(int i = 1;i < n;i++){
            //持有股票
            dp[i][0] = Math.max(dp[i - 1][0],-prices[i]);
            //不持有股票
            dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] + prices[i]);
        }

        return Math.max(dp[n - 1][0],dp[n - 1][1]);
    }

    //122.买卖股票的最佳时机II
    public static int maxProfit1(int[] prices) {
        int n = prices.length;

        //创建dp数组
        int[][] dp = new int[n][2];

        //初始化
        dp[0][0] = -prices[0];
        dp[0][1] = 0;

        //填表
        for(int i = 1;i < n;i++){
            //持有股票
            dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] - prices[i]);
            //不持有股票
            dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] + prices[i]);
        }

        return Math.max(dp[n - 1][0],dp[n - 1][1]);
    }

    public static void main(String[] args) {
        //1137.第N个泰波那契数列
        int tribonacciNum = tribonacci(40);
        System.out.println(tribonacciNum);

        //面试题 08.01. 三步问题
        int ret = waysToStep(10);
        System.out.println(ret);

        //746. 使用最小花费爬楼梯  解法一
        System.out.println(minCostClimbingStairs(new int[]{1, 2, 3, 4, 5}));

        //746. 使用最小花费爬楼梯  解法二
        System.out.println(minCostClimbingStairs1(new int[]{1, 2, 3}));

        //91.解码方式
        int count = numDecodings("10");
        System.out.println(count);

        //62.不同路径
        count = uniquePaths(3,5);
        System.out.println(count);

        //63.不同路径II
        count = uniquePathsWithObstacles(new int[][]{{0,0,0},{0,1,0},{0,0,0}});
        System.out.println(count);

        //LCR 166.珠宝的最高价值
        int max = jewelleryValue(new int[][]{{1,2,3},{4,5,6}});
        System.out.println(max);

        //931.下降路径最小和
//        ret = minFallingPathSum(new int[][]{{1,2,3},{4,5,6}});
        System.out.println(ret);

        //174.地下城游戏
        int min = calculateMinimumHP(new int[][]{{1,2,3},{4,5,6}});
        System.out.println(min);

        //面试题 17.16.按摩师按摩师
        int maxTime = massage(new int[]{1,2,3});
        System.out.println(maxTime);

        //LCR 091.粉刷房子
        min = minCost(new int[][]{{17,2,17},{16,16,5},{14,3,19}});
        System.out.println(min);

        //121.买卖股票的最佳时机
        int maxMoney = maxProfit(new int[]{1,2,3,4,5});
        System.out.println(maxMoney);

        //122.买卖股票的最佳时机II
        maxMoney = maxProfit1(new int[]{1,2,3,4,5});
        System.out.println(maxMoney);
    }
}
